/*
# ref     ;   https://baike.baidu.com/item/Trie/140945?fr=aladdin
# File    :   trie_tree.c
# Date    :   Sun, May 26, 2019 10:19:09 PM
*/

#include "trie_tree.h"
  
TrieNode Memory[1000000];
//int allocp = 0;
  
/*初始化*/
void InitTrieRoot(TrieNode* *pRoot)
{
    *pRoot=NULL;
}
  
/*创建新结点*/
TrieNode* CreateTrieNode()
{
    static int allocp = 0;
    int i;
    TrieNode *p;
    p = &Memory[allocp++];
    p->nCount = 1;
    for(i = 0; i < MAX; i++)
    {
        p->next[i]=NULL;
    }
    return p;
}
  
/*插入*/
void InsertTrie(TrieNode* *pRoot,char *s)
{
    int i,k;
    TrieNode*p;
    if(!(p = *pRoot))
    {
        p= *pRoot = CreateTrieNode();
    }
    i = 0;
    while(s[i])
    {
        k = s[i++] - 'a';//确定branch
        if(!p->next[k]){
            p->next[k] = CreateTrieNode();
        }else{
            p->next[k]->nCount++;
        }
        p=p->next[k];
    }
}
  
//查找
int SearchTrie(TrieNode* *pRoot,char *s)
{
    TrieNode *p;
    int i,k;
    if(!(p=*pRoot))
    {
        return 0;
    }
    i = 0;
    while(s[i])
    {
        k = s[i++]-'a';
        if(p->next[k]==NULL) return 0;
        p = p->next[k];
    }
    return p->nCount;
}
